package net.xuele.learn.dancing.lru;

import java.util.HashMap;

/**
 * @Author: yubo
 * @date: 11:11 2021/1/4
 * @Description: 类描述：也可以考虑直接实现LinkedHashMap
 */

public class LRUCache {

    /**
     * key -> Node(key, val)
     */
    private HashMap<Integer, Node> map;

    /**
     * Node(k1, v1) <-> Node(k2, v2)...
     */
    private DoubleList cache;
    /**
     * 最大容量
     */
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }


    /**
     * 将某个 key 提升为最近使用的
     *
     * @param key
     */
    private Node makeRecently(int key) {
        Node x = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队尾
        cache.addLast(x);
        return x;
    }


    /**
     * 添加最近使用的元素
     *
     * @param key
     * @param val
     */
    private Node addRecently(int key, int val) {
        Node x = new Node(key, val);
        // 链表尾部就是最近使用的元素
        cache.addLast(x);
        // 别忘了在 map 中添加 key 的映射
        map.put(key, x);
        return x;
    }

    /**
     * 删除某一个 key
     *
     * @param key
     */
    private Node deleteKey(int key) {
        Node x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 从 map 中删除
        map.remove(key);
        return x;
    }

    /**
     * 删除最久未使用的元素
     */
    private Node removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node deletedNode = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        // 从节点中获取map的key！！！否则，需要遍历map找到对应的key
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
        return deletedNode;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使用的
        Node node = makeRecently(key);
        return node.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }

        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 9, 0, 8, 19, 20, 22};
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int l = arr[i];
            max = Math.max(l, max);
            min = Math.min(l, min);
        }

        System.out.println(max + "----" + min);
    }
}
